// 40. [DFS递归只选1次数字] 组合总和 II
// https://leetcode.cn/problems/combination-sum-ii/ 错误
//给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates
//中所有可以使数字和为 target 的组合。 candidates
// 中的每个数字在每个组合中只能使用 一次 。 注意：解集不能包含重复的组合。 输入:
// candidates = [10,1,2,7,6,1,5], target = 8, 输出:[ [1,1,6], [1,2,5], [1,7],
//[2,6]
//]
//输入: candidates = [2,5,2,1,2], target = 5,
//输出:[
//[1,2,2],
//[5]
//]
//提示:1 <= candidates.length <= 100
// 1 <= candidates[i] <= 50
// 1 <= target <= 30

#include <bits/stdc++.h>

#include <vector>
using namespace std;

#define DEBUG_
#ifdef DEBUG_
#define PF(...) printf(__VA_ARGS__)
#define FRE(x)                    \
  freopen("d:/oj/" #x ".in", "r", \
          stdin)  //,freopen("d:/oj/"#x".out","w",stdout)
#define FREC fclose(stdin), fclose(stdout);
#else
#define PF(...)
#define FRE(x)
#define FREC
#endif

class Solution {
  vector<vector<int>> res_;
  vector<int> candidates_;
  void dfs(vector<int>& vtVisited, size_t idx, int target, vector<int> path) {
    if (idx == candidates_.size()) {
      return;
    }
    PF("=====I=%d, cand=%d, vi=%d, tar=%d\n", idx, candidates_[idx],
       vtVisited[idx], target);
    if (vtVisited[idx]) {
      return;
    }
    if (target == 0) {
      res_.push_back(path);
      PF("push=%d,%d,%d,%d\n", idx, candidates_[idx], vtVisited[idx], target);
      return;
    }
    dfs(vtVisited, idx + 1, target, path);
    if (target - candidates_[idx] >= 0) {
      path.push_back(candidates_[idx]);
      vtVisited[idx + 1] = true;
      dfs(vtVisited, idx + 1, target - candidates_[idx], path);
      path.pop_back();
      vtVisited[idx + 1] = false;
    }
  }

 public:
  vector<vector<int>> combinationSum2(const vector<int>& candidates,
                                      int target) {
    candidates_ = candidates;
    std::sort(candidates_.begin(), candidates_.end());
    // for (auto can : candidates_) PF("can=%d\n", can); PF("--%d==\n",
    // candidates_.size());// return res_;
    vector<int> vtVisited(candidates_.size(), false);
    // for (auto v : vtVisited) PF("v=%d\n",v); PF("--%d==\n",
    // vtVisited.size());
    dfs(vtVisited, 0, target, {});
    set<vector<int>> stRes;
    for (auto vt : res_) stRes.insert(vt);
    res_.clear();
    for (auto st : stRes) res_.push_back(st);
    return res_;
  }
};

// {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}, 27

int main() {
  Solution sol;
  vector<vector<int>> out =
      sol.combinationSum2({1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
                           1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
                          12);
  for (auto vt : out)
    for (auto n : vt) PF("%d,", n);
  PF("\n");
}
